BM37 二叉搜索树的最近公共祖先

https://www.nowcoder.com/practice/d9820119321945f588ed6a26f0a6991f

参考资料 236. 二叉树的最近公共祖先（后序遍历 DFS ，清晰图解）

祖先的定义： 若节点 p 在节点 root 的左（右）子树中，或 p = root，则称 root 是 p 的祖先。

最近公共祖先的定义： 设节点 root 为节点 p, q 的某公共祖先，若其左子节点 root.left 和右子节点 root.right 都不是 p, q 的公共祖先，则称 root 是 “最近的公共祖先” 。

根据以上定义，若 root 是 p, q 的 最近公共祖先 ，则只可能为以下情况之一：

• p 和 q 在 root 的子树中，且分列 root 的 异侧（即分别在左、右子树中）；
• p = root，且 q 在 root 的左或右子树中；
• q = root，且 p 在 root 的左或右子树中；

考虑通过递归对二叉树进行后序遍历，当遇到节点 p 或 q 时返回。从底至顶回溯，当节点 p, q 在节点 root 的异侧时，节点 root 即为最近公共祖先，则向上返回 root。

递归解析：

终止条件：

1. 当越过叶节点，则直接返回 null；
2. 当 root 等于 p, q，则直接返回 root；

递推工作：

1. 开启递归左子节点，返回值记为 left
2. 开启递归右子节点，返回值记为 right

返回值：

根据 left 和 right，可展开为四种情况；

1、当 left 和 right 同时为空：说明 root 的左 / 右子树中都不包含 p,q，返回 null；

2、当 left 和 right 同时不为空：说明 p,q 分列在 root 的异侧（分别在 左 / 右子树），因此 root 为最近公共祖先，返回 root；

3、当 left 为空，right 不为空：p,q 都不在 root 的左子树中，直接返回 right 。具体可分为两种情况：

• p,q 其中一个在 root 的右子树中，此时 right 指向 p（假设为 p）；
• p,q 两节点都在 root 的 右子树 中，此时的 right 指向最近公共祖先节点；

4、当 right 为空，left 不为空，同上

func lowestCommonAncestor( root *TreeNode, p, q int ) int {
    return lca(root, p, q).Val
}

func lca(root *TreeNode, p, q int) *TreeNode {
    if root == nil || root.Val == p || root.Val == q {
        return root
    }
    
    left := lca(root.Left, p, q)
    right := lca(root.Right, p, q)
    
    if left == nil && right == nil {
        return nil
    }
    
    if left == nil {
        return right
    }
    
    if right == nil {
        return left
    }
    
    return root
}